Recently, in various kinds of information equipment, a function which, when a user starts inputting a character string into a input form, selects a character string, that matches with the inputted character string, out of character strings recorded in advance, and suggests the selected character string as an input candidate is prevailing. The function is generally called ‘auto complete function’ (hereinafter, abbreviated as ‘auto complete’).
As a typical example to which the auto complete is applied, a search engine is exemplified. In the case of the search engine, as a specific example, when a user starts inputting a character string into a search form, the search engine extracts a character string, which matches with a character that the user is inputting, out of search key words which has been stored previously, and suggests the extracted character string to the user Hereinafter, the character string suggested to the user is described as ‘suggested candidate character string’.
Therefore, in the case that the search engine uses the auto complete, it is unnecessary for the user to input a whole of the search key word, and it is possible to input a key word, which the user wants to input, only by selecting any one out of the suggested candidate character strings.
Such the auto complete is applicable to not only the search engine but also every application program which requires inputting into an input form. As an example of the application other than the search engine, the Web browser which requires to input URL (Uniform Resource Locator), the electronic mail software which requires to input a mail address, the electronic commerce cite which requires to input a product name, or the like.
Moreover, NPL (non-patent literature) 1 discloses an example of an art that realizes the auto complete. According to the art which is disclosed by NPL 1, a suggested candidate character string, whose head portion is identical with a character string inputted by a user, is searched at a high speed.
A subject of the art which is disclosed by NPL 1 is language, whose character string inputted by the user with a key board is identical with description of the suggested candidate character string, such as English. Moreover, according to the art, the identity judgement on the head portion is carried out merely by checking whether or not the character cord of the character string inputted by the user is identical with the character cord of the suggested candidate character string. Therefore, it is difficult to apply the art, which is disclosed by NPL 1, to language, whose character string inputted by the user is not identical with description of the suggested candidate character string, such as Japanese language.
Specifically, in the case of inputting in the Japanese language, most of users input a character string, which the user wants to input, in a kana character by use of the romaji/kana input method or the like, and afterward converts the kana into the kanji (Chinese character).
(Note 1) Japanese language is mainly described by a combination of the kana character and the kanji (Chinese character). The kana is a Japanese syllabary based on the Chinese character and includes the hiragana and the katakana. Furthermore, the romaji is alphabetical description of the kana. For example, out of a character string (inputted character string),  and  are the kanji, and ,  and  are the hiragana. The katakana of ,  and  are ,  and  respectively. Accordingly, since it is conceivable that the inputting is almost finished at a time when the kana is converted into the kanji, it is too late to suggest the suggested candidate character string to the user after conversion into the kanji, and it is necessary to suggest the suggested candidate character string to the user at a time when inputting the kana.
Therefore, in order to apply the auto complete to the inputting in the Japanese language, it is necessary to beforehand estimate a kana-reading of a character string candidate which is collected from a Japanese language document and to compare a kana character string which is inputted by the user, and the kana-reading of the suggested candidate character string.
(Note 2) The kana-reading indicates how to read the kanji. For example, a kana-reading of  is  in the katakana or  in the hiragana.
As a method for estimating the kana-reading of the suggested candidate character string, a method of using a Japanese language dictionary, which describes relation between the suggested candidate character string and its kana-reading, is exemplified. According to the method, when a suggested candidate character string is collected from a Japanese language document, the suggested candidate character string is divided into portions each of which is identical with the description which exists in the dictionary. Next, kana-readings each of which is related to each portion are concatenated, and consequently the kana-reading of the suggested candidate character string is estimated.
The above-mentioned method for estimating the kana-reading by use of the dictionary can be realized by the method called the morphemic analysis. Furthermore, by use of each kana-reading of each portion of the suggested candidate character string, an index of the original suggested candidate character string is generated, and at a time when a user inputs a kana by use of the index, it is possible to suggest a suggested candidate character string which is related to the inputted kana.
Here, an art for suggesting the suggested candidate character string to the user in reply to the user's inputting the kana will be explained. PTL 1 discloses an art of searching information by use of the voice recognition.
According to the art which is disclosed by PTL 1, for example, a character string of  is divided into four words of , ,  and  with reference to the dictionary. Here, ,  and  are an abbreviation of  (supermarket), an example of a trade name and an example of a place name respectively. Then, by using kana-readings of four words which are described in the dictionary, a kana reading of   is estimated.
(Note 3)  is a kana-reading in the katakana of the  which is the kanji.
When the user inputs  with the voice input method, a partial character string of  whose head portion is identical with  is searched, and the original character string of  including the partial character string is estimated and then the original character string is suggested to the user.